package com.kehao.newcoder;


public class NC12Solution {

    private static class TreeNode {
        int val;
        TreeNode left;
        TreeNode right;

        TreeNode(int x) {
            val = x;
        }
    }

    public TreeNode reConstructBinaryTree(int[] pre, int[] vin) {
        return reConstructBinaryTree(pre, 0, pre.length, vin, 0, pre.length);
    }

    private TreeNode reConstructBinaryTree(int[] pre, int preStart, int preEnd, int[] vin, int vinStart, int vinEnd) {
        if (preStart >= preEnd) {
            return null;
        } else if (preStart + 1 == preEnd) {
            return new TreeNode(pre[preStart]);
        }else {
            TreeNode root = new TreeNode(pre[preStart]);
            for (int i = vinStart; i < vinEnd; i++) {
                if(vin[i]==pre[preStart]){
                    root.left = reConstructBinaryTree(pre,preStart+1,i-vinStart+preStart+1,vin,vinStart,i);
                    root.right = reConstructBinaryTree(pre,i-vinStart+preStart+1,preEnd,vin,i+1,vinEnd);
                }
            }
            return root;
        }
    }
}
